home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 2 / Atari Mega Archive CD - Volume 2.iso / minix / up1510b.tgz / up1510b / src / commands / compress.c < prev    next >
C/C++ Source or Header  |  1990-07-23  |  38KB  |  1,604 lines
  1. /* compress - Reduce file size using Modified Lempel-Ziv encoding */
  2.  
  3. /*
  4.  * compress.c - File compression ala IEEE Computer, June 1984.
  5.  *
  6.  * Authors:    Spencer W. Thomas    (decvax!harpo!utah-cs!utah-gr!thomas)
  7.  *        Jim McKie        (decvax!mcvax!jim)
  8.  *        Steve Davies        (decvax!vax135!petsd!peora!srd)
  9.  *        Ken Turkowski        (decvax!decwrl!turtlevax!ken)
  10.  *        James A. Woods        (decvax!ihnp4!ames!jaw)
  11.  *        Joe Orost        (decvax!vax135!petsd!joe)
  12.  *
  13.  *        Richard Todd        Port to MINIX
  14.  *        Andy Tanenbaum        Cleanup
  15.  *
  16.  *
  17.  * Algorithm from "A Technique for High Performance Data Compression",
  18.  * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
  19.  *
  20.  * Usage: compress [-dfvc] [-b bits] [file ...]
  21.  * Inputs:
  22.  *    -d:        If given, decompression is done instead.
  23.  *
  24.  *      -c:         Write output on stdout.
  25.  *
  26.  *      -b:         Parameter limits the max number of bits/code.
  27.  *
  28.  *    -f:        Forces output file to be generated, even if one already
  29.  *            exists, and even if no space is saved by compressing.
  30.  *            If -f is not used, the user will be prompted if stdin is
  31.  *            a tty, otherwise, the output file will not be overwritten.
  32.  *
  33.  *      -v:        Write compression statistics
  34.  *
  35.  *     file ...:   Files to be compressed.  If none specified, stdin
  36.  *            is used.
  37.  * Outputs:
  38.  *    file.Z:        Compressed form of file with same mode, owner, and utimes
  39.  *     or stdout   (if stdin used as input)
  40.  *
  41.  * Assumptions:
  42.  *    When filenames are given, replaces with the compressed version
  43.  *    (.Z suffix) only if the file decreases in size.
  44.  * Algorithm:
  45.  *     Modified Lempel-Ziv method (LZW).  Basically finds common
  46.  * substrings and replaces them with a variable size code.  This is
  47.  * deterministic, and can be done on the fly.  Thus, the decompression
  48.  * procedure needs no input table, but tracks the way the table was built.
  49.  */
  50.  
  51.  
  52. #define AZTEC86 1
  53.  
  54. #define    min(a,b)    ((a>b) ? b : a)
  55.  
  56. /*
  57.  * Set USERMEM to the maximum amount of physical user memory available
  58.  * in bytes.  USERMEM is used to determine the maximum BITS that can be used
  59.  * for compression.
  60.  *
  61.  * SACREDMEM is the amount of physical memory saved for others; compress
  62.  * will hog the rest.
  63.  */
  64. #ifndef SACREDMEM
  65. #define SACREDMEM    0
  66. #endif
  67.  
  68. #ifndef USERMEM
  69. # define USERMEM     450000    /* default user memory */
  70. #endif
  71.  
  72. #define REGISTER register
  73. #define DOTZ ".Z"
  74.  
  75. #ifdef AZTEC86 
  76. void prratio(),cl_block(),cl_hash(),output(),decompress(),
  77. copystat(),writeerr(),compress(),Usage(),version();
  78. #ifdef AZTECBITS
  79. # define BITS   AZTECBITS
  80. #else
  81. # define BITS 13
  82. #endif
  83. # undef USERMEM
  84. #endif /* AZTEC86 */
  85.  
  86. #ifdef USERMEM
  87. # if USERMEM >= (433484+SACREDMEM)
  88. #  define PBITS    16
  89. # else
  90. #  if USERMEM >= (229600+SACREDMEM)
  91. #   define PBITS    15
  92. #  else
  93. #   if USERMEM >= (127536+SACREDMEM)
  94. #    define PBITS    14
  95. #   else
  96. #    if USERMEM >= (73464+SACREDMEM)
  97. #     define PBITS    13
  98. #    else
  99. #     define PBITS    12
  100. #    endif
  101. #   endif
  102. #  endif
  103. # endif
  104. # undef USERMEM
  105. #endif /* USERMEM */
  106.  
  107. #ifdef PBITS        /* Preferred BITS for this memory size */
  108. # ifndef BITS
  109. #  define BITS PBITS
  110. # endif
  111. #endif /* PBITS */
  112.  
  113. #if BITS == 16
  114. # define HSIZE    69001        /* 95% occupancy */
  115. #endif
  116. #if BITS == 15
  117. # define HSIZE    35023        /* 94% occupancy */
  118. #endif
  119. #if BITS == 14
  120. # define HSIZE    18013        /* 91% occupancy */
  121. #endif
  122. #if BITS == 13
  123. # define HSIZE    9001        /* 91% occupancy */
  124. #endif
  125. #if BITS <= 12
  126. # define HSIZE    5003        /* 80% occupancy */
  127. #endif
  128.  
  129.  
  130. /*
  131.  * a code_int must be able to hold 2**BITS values of type int, and also -1
  132.  */
  133. #if BITS > 15
  134. typedef long int    code_int;
  135. #else
  136. typedef int        code_int;
  137. #endif
  138.  
  139. #ifdef SIGNED_COMPARE_SLOW
  140. typedef unsigned long int count_int;
  141. typedef unsigned short int count_short;
  142. #else
  143. typedef long int      count_int;
  144. #endif
  145.  
  146. #ifdef NO_UCHAR
  147.  typedef char    char_type;
  148. #else
  149.  typedef    unsigned char    char_type;
  150. #endif /* UCHAR */
  151. char_type magic_header[] = { "\037\235" };    /* 1F 9D */
  152.  
  153. /* Defines for third byte of header */
  154. #define BIT_MASK    0x1f
  155. #define BLOCK_MASK    0x80
  156. /* Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is
  157.    a fourth header byte (for expansion).
  158. */
  159. #define INIT_BITS 9            /* initial number of bits/code */
  160.  
  161. #include <sys/types.h>
  162. #include <sys/stat.h>
  163. #include <fcntl.h>
  164. #include <ctype.h>
  165. #include <signal.h>
  166. #include <stdio.h>
  167.  
  168. #define ARGVAL() (*++(*argv) || (--argc && *++argv))
  169.  
  170. int n_bits;                /* number of bits/code */
  171. int maxbits = BITS;            /* user settable max # bits/code */
  172. code_int maxcode;            /* maximum code, given n_bits */
  173. code_int maxmaxcode = 1 << BITS;    /* should NEVER generate this code */
  174. #ifdef COMPATIBLE        /* But wrong! */
  175. # define MAXCODE(n_bits)    (1 << (n_bits) - 1)
  176. #else
  177. # define MAXCODE(n_bits)    ((1 << (n_bits)) - 1)
  178. #endif /* COMPATIBLE */
  179.  
  180. #ifndef AZTEC86
  181.     count_int htab [HSIZE];
  182.     unsigned short codetab [HSIZE];
  183. #else
  184.     count_int *htab;
  185.     unsigned short *codetab;
  186. #    define HTABSIZE ((unsigned)(HSIZE*sizeof(count_int)))
  187. #    define CODETABSIZE ((unsigned)(HSIZE*sizeof(unsigned short)))
  188.  
  189.  
  190. #define htabof(i)    htab[i]
  191. #define codetabof(i)    codetab[i]
  192. #endif    /* XENIX_16 */
  193. code_int hsize = HSIZE;            /* for dynamic table sizing */
  194. count_int fsize;
  195.  
  196. /*
  197.  * To save much memory, we overlay the table used by compress() with those
  198.  * used by decompress().  The tab_prefix table is the same size and type
  199.  * as the codetab.  The tab_suffix table needs 2**BITS characters.  We
  200.  * get this from the beginning of htab.  The output stack uses the rest
  201.  * of htab, and contains characters.  There is plenty of room for any
  202.  * possible stack (stack used to be 8000 characters).
  203.  */
  204.  
  205. #define tab_prefixof(i)    codetabof(i)
  206. #ifdef XENIX_16
  207. # define tab_suffixof(i)    ((char_type *)htab[(i)>>15])[(i) & 0x7fff]
  208. # define de_stack        ((char_type *)(htab2))
  209. #else    /* Normal machine */
  210. # define tab_suffixof(i)    ((char_type *)(htab))[i]
  211. # define de_stack        ((char_type *)&tab_suffixof(1<<BITS))
  212. #endif    /* XENIX_16 */
  213.  
  214. code_int free_ent = 0;            /* first unused entry */
  215. int exit_stat = 0;
  216.  
  217. code_int getcode();
  218.  
  219. void Usage() {
  220. #ifdef DEBUG
  221. fprintf(stderr,"Usage: compress [-dDVfc] [-b maxbits] [file ...]\n");
  222. }
  223. int debug = 0;
  224. #else
  225. fprintf(stderr,"Usage: compress [-dfvcV] [-b maxbits] [file ...]\n");
  226. }
  227. #endif /* DEBUG */
  228. int nomagic = 0;    /* Use a 3-byte magic number header, unless old file */
  229. int zcat_flg = 0;    /* Write output on stdout, suppress messages */
  230. int quiet = 0;        /* don't tell me about compression */
  231.  
  232. /*
  233.  * block compression parameters -- after all codes are used up,
  234.  * and compression rate changes, start over.
  235.  */
  236. int block_compress = BLOCK_MASK;
  237. int clear_flg = 0;
  238. long int ratio = 0;
  239. #define CHECK_GAP 10000    /* ratio check interval */
  240. count_int checkpoint = CHECK_GAP;
  241. /*
  242.  * the next two codes should not be changed lightly, as they must not
  243.  * lie within the contiguous general code space.
  244.  */ 
  245. #define FIRST    257    /* first free entry */
  246. #define    CLEAR    256    /* table clear output code */
  247.  
  248. int force = 0;
  249. char ofname [100];
  250. #ifdef DEBUG
  251. int verbose = 0;
  252. #endif /* DEBUG */
  253.  
  254. #ifndef METAWARE
  255. #ifdef AZTEC86
  256. void
  257. #else
  258. int
  259. #endif
  260. (*bgnd_flag)();
  261. #endif
  262.  
  263. int do_decomp = 0;
  264.  
  265.  
  266. void main( argc, argv )
  267. REGISTER int argc; char **argv;
  268. {
  269.     int overwrite = 0;    /* Do not overwrite unless given -f flag */
  270.     char tempname[100];
  271.     char **filelist, **fileptr;
  272.     char *cp;extern char *strrchr(), *malloc();
  273.     struct stat statbuf;
  274. #ifndef METAWARE
  275.     extern void onintr(), oops();
  276.     if ( (bgnd_flag = signal ( SIGINT, SIG_IGN )) != SIG_IGN ) {
  277.     signal ( SIGINT, onintr );
  278.     signal ( SIGSEGV, oops );
  279.     }
  280. #endif
  281. #ifdef AZTEC86
  282. #ifdef METAWARE
  283.     _setmode(NULL,_ALL_FILES_BINARY);
  284.     _setmode(stdin,_BINARY);
  285.     _setmode(stdout,_BINARY);
  286.     _setmode(stderr,_TEXT);
  287. #endif
  288.     if (NULL == (htab = (count_int *)malloc(HTABSIZE)))
  289.     {
  290.         fprintf(stderr,"Can't allocate htab\n");
  291.         exit(1);
  292.     }
  293.     if (NULL == (codetab = (unsigned short *)malloc(CODETABSIZE)))
  294.     {
  295.         fprintf(stderr,"Can't allocate codetab\n");
  296.         exit(1);
  297.     }
  298. #endif
  299. #ifdef COMPATIBLE
  300.     nomagic = 1;    /* Original didn't have a magic number */
  301. #endif /* COMPATIBLE */
  302.  
  303.     filelist = fileptr = (char **)(malloc((unsigned)(argc * sizeof(*argv))));
  304.     *filelist = NULL;
  305.  
  306.     if((cp = strrchr(argv[0], '/')) != 0) {
  307.     cp++;
  308.     } else {
  309.     cp = argv[0];
  310.     }
  311.     if(strcmp(cp, "uncompress") == 0) {
  312.     do_decomp = 1;
  313.     } else if(strcmp(cp, "zcat") == 0) {
  314.     do_decomp =